236. Lowest Common Ancestor of a Binary Tree(medium)

題目敘述
給定一棵二元樹，尋找兩個節點的最近公共祖先（LCA）。最近公共祖先是兩個節點 p 和 q 的一個祖先節點，它是距離這兩個節點最近的共同祖先。

解題思路

1. 建立紀錄父節點關係的陣列 (parent)：從根節點開始，遞迴遍歷樹，並記錄每個節點的父節點。
   • parent[i] 為節點 i 的父節點。
2. 記錄節點 p 的所有祖先 ：根據步驟 1 構建的陣列 (parent)，從節點 p 開始向上搜尋，將所有的祖先節點（包括自己）加入到一個 set 中(p_ancestors)，直到根節點。
3. 尋找 q 的祖先並比對：從節點 q 開始向上搜尋，並檢查其祖先是否已經存在於 p 的祖先集合(p_ancestors)中。一旦發現 q 的祖先出現在 p 的祖先集合中，該節點即為最近公共祖先（LCA）

class Solution {
public:
    unordered_map<TreeNode*, TreeNode*> parent;
    
    // 建立父節點的映射
    void buildParent(TreeNode* root) {
        if (!root) return;
        if (root->left) {
            parent[root->left] = root;
            buildParent(root->left);
        }
        if (root->right) {
            parent[root->right] = root;
            buildParent(root->right);
        }
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        parent[root] = NULL;
        buildParent(root);   
        
        unordered_set<TreeNode*> p_ancestors;
        
        // Add all ancestors of node p to the set
        while (p) {
            p_ancestors.insert(p);
            p = parent[p];
        }
        
        // Find the ancestors of q and compare them with the ancestor set of p
        while (q) {
            if (p_ancestors.count(q)) {
                return q;
            }
            q = parent[q];
        }
        
        return root; 
    }
};

時間複雜度: O(n)，n 是節點的數量